package org.hhchat.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * Created this one by HMH on 2017/3/30.
 * https://leetcode.com/problems/n-queens/description/
 * N 皇后
 */
public class code51_easy {
    public static class Solution {
        class que{
            int x;
            int y;

            public que(int x, int y) {
                this.x = x;
                this.y = y;
            }

            boolean isValidate(int col, int row) {
                if (col == x || row == y || row + x == y + col || row + col == x + y) {
                    return false;
                }
                return true;
            }
        }

        List<que> qlist = new ArrayList<>();
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<>();
            char[][] board = new char[n][n];
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    board[i][j] = '.';
                }
            }
            dfs(result, board, 0);
            return result;

        }



        private void dfs(List<List<String>> result, char[][] board, int col) {
            int len = board.length;
            if (col == len) {
                result.add(construts(board));
            }
            for(int i=0;i<len;i++) {
                if (validation(col, i)) {
                    qlist.add(new que(col, i));
                    board[i][col] = 'Q';
                    dfs(result, board, col + 1);
                    qlist.remove(qlist.size()-1);
                    board[i][col] = '.';
                }
            }
        }

        private boolean validation(int x,int y) {
            for (que q : qlist) {
                if(!q.isValidate(x,y))
                    return false;
            }
            return true;
        }

        private List<String> construts(char[][] board) {
            List<String> list = new ArrayList<>();
            int n = board.length;
            for(int i=0;i<n;i++) {
                list.add(new String(board[i]));
            }
            return list;
        }
    }

    public static void main(String[] args){
        System.out.println(new Solution().solveNQueens(4));
    }
}
